package leetcode.D200.T154;

class Solution {
//    public int findMin(int[] nums) {
//        int left = 0, right = nums.length-1;
//        while(left < right) {
//            int mid = left + (right-left) / 2;
//            if(nums[left] == nums[right]) {
//                if(nums[mid] == nums[left]) {
//                    left++;
//                } else if(nums[mid] < nums[right]) {
//                    right = mid;
//                } else {
//                    left = mid + 1;
//                }
//            } else if (nums[left] > nums[right]){
//                if(nums[mid] >= nums[left]) {
//                    left = mid + 1;
//                } else {
//                    right = mid;
//                }
//            } else {
//                break;
//            }
//        }
//        return nums[left];
//    }

    public int findMin(int[] nums) {
        int left = 0, right = nums.length-1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[left] < nums[right]) {
                return nums[left];
            } else if(nums[left] > nums[right]) {
                if(nums[mid] > nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            } else {
                if(nums[mid] > nums[left]) {
                    left = mid + 1;
                } else if(nums[mid] < nums[left]) {
                    right = mid;
                } else {
                    right--;//left++;//都可以
                }
            }
        }
        return nums[left];
    }
}